The present invention relates to electronic. memories, and more particularly to electronic first-in-first-out memories. Even more particularly, the present invention relates to hazard-free detection of full and empty conditions in electronic first-in-first-out memories.
Electronic memories are common in the field of digital electronics. Such memories have numerous applications and are numerous in type. A particular application of electronic memories is a first-in-first-out memory, or FIFO memory. Some FIFO memory employ a bank of logic gates clocked by separate load and unload clocks. For example, a FIFO memory is available as Type SN74S225 from Texas Instruments, Inc. of Dallas, Tex. The SN74S225 FIFO memory is packaged in a single integrated circuit chip and holds sixteen words of five bits.
One alternative to the bank-of-logic-gates-type FIFO memory employs random access memory, or RAM. Such RAM-based FIFO memories employ conventional RAM memories, such as those that are used in micro computer or state machine-based devices. Unfortunately, these FIFO memories are susceptible to false indications that they are full or empty, when in fact they are not full or empty, and as a result, often employ means for coordinating (but not necessarily synchronizing) the read and write circuitry used to read and write the binary signals from and to the RAM employed by the RAM-based FIFO memories. Unfortunately, FIFO memories such as the SN74S225 FIFO memory require a significant setup time at each of the gates that comprise the FIFO memory. This setup time, unfortunately, limits the speed with which the FIFO memory can be written or read.
A further problem with FIFO memories such as the SN74S225 FIFO memory is that data must propagate through each of a plurality of sets of latches within the FIFO memory before emerging at the outputs of the FIFO memory. Thus, it can take several clock cycles before data presented at the inputs is available at the outputs, potentially wasting valuable processing time.
Other RAM-based FIFO memories employ additional unused memory locations to assure that read and write pointers of the FIFO memories do not simultaneously point to the same location within the RAM, thus preventing or minimizing the risk of erroneous empty and full conditions at the expense of unused RAM. Finally, some RAM-based FIFO memories dedicate empty and full latches to indicate whether the FIFO memory is empty or full. Unfortunately, such latches are prone to falsely indicating empty or full conditions and to indicating both empty and full conditions simultaneously.
To illustrate this problem, reference is made to FIG. 1, where pointers used with a RAM-based FIFO memory are functionally represented. The FIFO memory has four locations that correspond to the pointer states labelled 0, 1, 2 and 3 as in FIG. 1. A read pointer R is shown pointing to location 0, and a write pointer W is shown transitioning from location 3 to location 0, as would be the case immediately after the last remaining location within the FIFO memory has been written to, i.e., filled. Each time the FIFO memory is written to, the write pointer W advances to the next location, such as is shown in FIG. 1 wherein the write pointer W is transitioning from location 3 to location 0.
As the write pointer W transitions from pointing to location 3 to pointing to location 0 it may pass through an indefinite state, which is caused by unequal delays in the logic circuitry used to implement the write pointer W, e.g., logic circuitry used to implement a write counter. Thus, if an attempt is made to write to the FIFO memory while the write pointer W is transitioning, one of three possibilities exists. First, the write pointer W may be read as pointing to location 0, in which case the FIFO memory should correctly indicate that it is full. However, the location of the write pointer W and the read pointer R, i.e., pointing to location 0, is the same for the full condition as it is for the empty condition. Due to this ambiguity, there is significant risk that the memory will indicate that an empty condition exists or that both an empty and a full condition exist, instead of correctly indicating that a full condition exists. Second, the memory may indicate that the write pointer W is pointing to location 3, in which case there is a risk that information will be written to location 3, overwriting information already stored at location 3. Finally, there is a risk that the write pointer W will point to a meaningless or indeterminate location as the result of its transitioning from location 3 to location 0. In which case, the result is unpredictable.
Referring next to FIG. 2, the RAM-based FIFO memory is again illustrated, having four memory locations labelled 0, 1, 2 and 3 in FIG. 1. The write pointer W is pointing to location 0 and the read pointer R is transitioning from location 3 to location 0. Each time the FIFO memory is read from, the read pointer R advances one state, such as is shown in FIG. 2 wherein the read pointer R is transitioning from location 3 to location 0.
As indicated with the write pointer W in FIG. 1, the read pointer R in FIG. 2 may transition through a meaningless or indeterminate condition before settling to point at location 0. The same three potential problems described in FIG. 1 with respect to the write pointer W, affect the read pointer R in FIG. 2.
Therefore, as can be seen, improvements are needed in the detection of full and empty conditions in FIFO memories.